package com.banmoon.datastructure.BinarySearchTree;

import lombok.Data;
import lombok.NoArgsConstructor;

import java.util.Arrays;
import java.util.Objects;
import java.util.Optional;

public class BinarySearchTree {

    private Node root;

    /**
     * 生成二叉查找树
     * @param values
     * @return
     */
    public static BinarySearchTree generate(int[] values) {
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        Arrays.stream(values).forEach(binarySearchTree::add);
        return binarySearchTree;
    }

    /**
     * 添加节点
     * @param value
     */
    public void add(int value) {
        if (Objects.isNull(root))
            this.root = new Node(value);
        else
            root.add(value);
    }

    /**
     * 中序遍历
     */
    public void show() {
        if (Objects.nonNull(this.root))
            this.root.show();
    }

    /**
     * 查找节点
     * @param value
     * @return
     */
    public Node search(int value) {
        if (Objects.isNull(this.root))
            return null;
        return root.search(value);
    }

    /**
     * 删除节点
     * @param value
     * @return
     */
    public Node delete(int value) {
        if (Objects.isNull(this.root))
            return null;
        return this.root.delete(this, value, null);
    }

    /**
     * 重新设置左节点或右节点的值
     * @param originNode
     * @param targetNode
     */
    public void setNode(Node parent, Node originNode, Node targetNode) {
        // 如果父节点是null，则说明是根节点
        if (parent == null)
            this.root = targetNode;
        else if (parent.getLeftNode() == originNode)
            parent.setLeftNode(targetNode);
        else if (parent.getRightNode() == originNode)
            parent.setRightNode(targetNode);
    }

}

@Data
@NoArgsConstructor
class Node {
    private int value;
    private Node leftNode;
    private Node rightNode;

    public Node(int value) {
        this.value = value;
    }

    public void add(int value) {
        if (value < this.value) {
            if (Objects.nonNull(this.leftNode))
                this.leftNode.add(value);
            else
                this.leftNode = new Node(value);
        } else {
            if (Objects.nonNull(this.rightNode))
                this.rightNode.add(value);
            else
                this.rightNode = new Node(value);
        }
    }

    public void show() {
        if (Objects.nonNull(this.leftNode))
            this.leftNode.show();
        System.out.print(this.value + ", ");
        if (Objects.nonNull(this.rightNode))
            this.rightNode.show();
    }

    public Node search(int value) {
        if (this.value == value)
            return this;
        else if (this.value > value && Objects.nonNull(this.leftNode))
            return this.leftNode.search(value);
        else if (this.value < value && Objects.nonNull(this.rightNode))
            return this.rightNode.search(value);
        return null;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }

    /**
     * 分为3种情况
     * 1、删除叶子节点
     * 2、删除仅有一个节点的父节点的情况
     * 3、删除两个节点的父节点的情况
     * @param tree 当前的二叉查找树
     * @param value 删除的值
     * @param parent 当前节点的父节点
     * @return
     */
    public Node delete(BinarySearchTree tree, int value, Node parent) {
        if (this.value == value) {
            // 叶子节点，左节点和右节点都为空
            if (Objects.isNull(this.leftNode) && Objects.isNull(this.rightNode)) {
                tree.setNode(parent, this, null);
            }
            // 内部节点，且左节点和右节点都存在，
            else if (Objects.nonNull(this.leftNode) && Objects.nonNull(this.rightNode)) {
                Node tempLeftNode = this.leftNode;
                Node tempRightNode = this.rightNode;
                // 删除右子树中，最小的节点
                Node minNode = this.rightNode.deleteMin(this);
                // 最小的节点，用于替换该节点
                tree.setNode(parent, this, minNode);
                minNode.setLeftNode(tempLeftNode==minNode ? null : tempLeftNode);
                minNode.setRightNode(tempRightNode==minNode ? null : tempRightNode);
            }
            // 内部节点，左节点或右节点仅有一个存在
            else {
                Node node = Optional.of(this.leftNode).orElse(this.rightNode);
                tree.setNode(parent, this, node);
            }
            return this;
        } else if (this.value > value && Objects.nonNull(this.leftNode)) {
            return this.leftNode.delete(tree, value, this);
        } else if (this.value < value && Objects.nonNull(this.rightNode)) {
            return this.rightNode.delete(tree, value, this);
        }
        return null;
    }

    /**
     * 删除最小的那个节点
     * @param parent 当前节点的父节点
     * @return
     */
    private Node deleteMin(Node parent) {
        if (Objects.nonNull(this.leftNode)) {
            return this.leftNode.deleteMin(this);
        } else {
            parent.setLeftNode(this.rightNode);
        }
        return this;
    }

}